package main

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func inorderTraversal(root *TreeNode) []int {
	var result []int
	var stack []*TreeNode
	n := root
	for n != nil || len(stack) > 0 {
		for n != nil {
			stack = append(stack, n)
			n = n.Left
		}
		n = stack[len(stack)-1]
		stack = stack[0 : len(stack)-1]
		result = append(result, n.Val)
		n = n.Right
	}
	return result
}

func main() {
	root := &TreeNode{Val: 3}
	n1 := &TreeNode{Val: 9}
	n2 := &TreeNode{Val: 20}
	n3 := &TreeNode{Val: 15}
	n4 := &TreeNode{Val: 7}
	root.Left = n1
	root.Right = n2
	n2.Left = n3
	n2.Right = n4
	ret := inorderTraversal(root)
	println(ret)

}
